package org.anderground.app.controller.algorithms;

import static org.anderground.core.Logger.log;
import static org.anderground.core.Logger.logBegin;
import static org.anderground.core.Logger.logEnd;

import java.util.ArrayList;
import java.util.Observable;
import java.util.Observer;

import org.anderground.app.model.AppModel;
import org.anderground.core.model.Line;
import org.anderground.core.model.Station;

/**
 * Dijkstra's shortest path algorithm
 * 
 * @author Eldar Abusalimov (eldar.abusalimov@gmail.com)
 */
public class MetroRouter implements Observer {

	/** singleton instance */
	private static MetroRouter instance = new MetroRouter();

	/** the graph to search */
	private Graph graph;

	/** start station from which begins search */
	private Station fromStation;

	/** sorted list to store the next pass unvisited vertices */
	private SortedVertexList nextPassUnvisiteds;

	/**
	 * private constructor
	 */
	private MetroRouter() {
		AppModel.getInstance().addObserver(this);
		graph = new Graph(AppModel.getInstance().getData());
	}

	/**
	 * @return the instance
	 */
	public static MetroRouter getInstance() {
		return instance;
	}

	public void update(Observable observable, Object data) {
		if (observable == AppModel.getInstance()) {
			graph = new Graph(AppModel.getInstance().getData());
		}
	}

	/**
	 * This method performs searching of the shortest ways between stationFrom
	 * and all others by using Dijkstra's algorithm
	 * 
	 * @param fromStation
	 *            the station from which begins search
	 * @throws IllegalArgumentException
	 *             if the presented station is null or does not belong to the
	 *             model
	 */
	public synchronized void prepare(Station fromStation) {

		if (fromStation == null) {
			throw new IllegalArgumentException("fromStation cannot be null");
		} else if (this.fromStation == fromStation) {
			return;
		}
		this.fromStation = fromStation;

		nextPassUnvisiteds = new SortedVertexList(0);

		logBegin("Starting new Dijkstra's calculation");
		log("reset each vertex");
		this.graph.reset();

		for (Line line : fromStation.getLines()) {
			Vertex fromVertex = graph.getVerticesHash().get(fromStation, line);
			if (fromVertex == null) {
				throw new IllegalArgumentException(
						"presented station does not belong to the model: "
								+ fromStation + " at " + line);

			}
			fromVertex.setAsStart();
			nextPassUnvisiteds.add(fromVertex);
			Way currentPassWay = fromVertex.passWayMap.get(0);
			log("adding vertex (total ways: "
					+ fromVertex.passWayMap.size()
					+ ", station "
					+ fromVertex.getStation()
					+ ", reach time: "
					+ (currentPassWay.transferDistance + currentPassWay.tunnelDistance)
					+ ")");
		}

		log("Starting algorithm");

		SortedVertexList unvisiteds;
		do {
			unvisiteds = nextPassUnvisiteds;
			nextPassUnvisiteds = new SortedVertexList(unvisiteds.getPass() + 1);
			log("pass " + unvisiteds.getPass() + " (" + unvisiteds.size()
					+ " enter points)");

			while (!unvisiteds.isEmpty()) {
				Vertex vertex = unvisiteds.get(0);
				int pass = unvisiteds.getPass();
				for (Edge edge : vertex.getEdges()) {
					Vertex neighbor = edge.getToVertex();
					if (neighbor.isVisited(pass)) {
						continue;
					}
					// Update distance and position in sorted list on those
					// vertices which can be immediately reached from the
					// current vertex.
					neighbor.tryWay(edge, unvisiteds, nextPassUnvisiteds);
				}
				// Mark the current vertex as visited.
				vertex.setAsVisited(pass);
				unvisiteds.remove(vertex);
			}

		} while (!nextPassUnvisiteds.isEmpty());

		logEnd("Dijkstra's algorithm successfully completed");
	}

	/**
	 * get all possible routes between the stations
	 * 
	 * @param fromStation
	 * @param toStation
	 * 
	 * @return routes array
	 * @throws IllegalArgumentException
	 *             if the presented stations are null or do not belong to the
	 *             model
	 */
	public Route[] searchRoutes(Station fromStation, Station toStation) {

		prepare(fromStation);

		Vertex destinationPseudoVertex = new Vertex(toStation);
		ArrayList<Vertex> destinationVertices = new ArrayList<Vertex>();

		for (Line line : toStation.getLines()) {
			Vertex destinationVertex = graph.getVerticesHash().get(toStation,
					line);

			if (destinationVertex == null) {
				throw new IllegalArgumentException(
						"presented station does not belong to the model: "
								+ toStation + " at " + line);
			}
			log("Vertex for station " + toStation.getName() + " at line "
					+ line.getName() + " found");
			destinationVertices.add(destinationVertex);
		}

		for (int pass = 0; pass < nextPassUnvisiteds.getPass(); pass++) {

			for (Vertex destinationVertex : destinationVertices) {
				Way vertexWay = destinationVertex.passWayMap.get(pass);
				if (vertexWay != null) {
					destinationPseudoVertex.tryWay(new Edge(destinationVertex,
							destinationPseudoVertex), vertexWay);
				}
			}
		}

		Route[] routes = new Route[destinationPseudoVertex.passWayMap.size()];
		log("total routes: " + routes.length);
		int i = 0;
		for (Way way : destinationPseudoVertex.passWayMap.values()) {
			routes[i++] = new Route(way);
		}

		return routes;
	}

}
